package DynamicProgrammingPackage;

/**
 * @author Lzm
 * @version 1.0
 */
public class lastStoneWeightII_ {
  public static void main(String[] args) {
    int[] stones = new int[]{2,7,4,1,8,1};
    System.out.println(lastStoneWeightII(stones));
  }

  // 思路: 将stones分成两个集合, 且两集合相撞之后的重量尽可能相同, 01背包问题
  // 求一个背包, 这个背包中的元素是stones的子集, 且元素和为stones元素和的一半
  // 1. dp[i]表示容量为j的背包的价值为dp[j]
  // 2. 递推公式: dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i])
  // 3. 初始化: dp[0] = 0;
  // 4. 遍历顺序: 先物品后背包且倒序遍历背包
  public static int lastStoneWeightII(int[] stones) {
    int[] weight = stones;
    int[] value = stones;
    int sum = sum(stones);
    int target = sum(stones) / 2;
    int[] dp = new int[1501];
    for (int i = 0 ; i < stones.length ; i++){
      for (int j = target ; j >= weight[i] ;j--){
        dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i]);
      }
    }
    return sum - dp[target] - dp[target];
  }
  public static int sum(int[] nums){
    int sum = 0;
    for (int num : nums) {
      sum += num;
    }
    return sum;
  }
}
